HW#1 --- last modified February 06 2019 04:13:25..

Solution set.

Due date: Feb 15

Files to be submitted:
  Hw1.pdf

Purpose: To refresh our memories with regard to Turing Machines, asymptotic notations, and proofs.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO1 -- Exhibit a simulation of one machine model with another. For instance, a Turing machine by a RAM.

Specification:

For this homework I would like you to write up solutions to the problems below. If possible, write up the homework in LaTeX. If you use Word, format any math by using the math equation editor. Once you have prepared your solution output it as a PDF and submit it as Hw1.pdf. Be aware that the maximum-sized document that the upload system supports is 10 MB.

1. Carefully show each of the following statements (1/2pt each):
   1. `n^100 = o(2^n)`,
   2. `\sum_{i=1}^n i = \Omega(n^2)`,
   3. `n^2+n+1 = \Theta(3n^2)`,
   4. `\sum_{i=1}^n log i = O(n \cdot log n)`.
2. Give the formal description of a TM (completely specify the triple `(Q, \Gamma, \delta)`) that computes the function from `{0,1}^{\star}` to `{0,1}` which has value 1 if the string contains exactly three 0's and 0 otherwise.
3. Carefully show the function `n \cdot log n` is time constructible.
4. A random access memory Turing Machine is a like a our usual Turing machine model except rather than have the input on a read only tape, the first tape of the machine serves as a way to look up symbols from the input. In particular, the machine can write a binary number `j` on its first tape between the start of tape symbol and the tape head, then enter a special query state, and in the next time step it switches to a query result state and all the other tapes are unchanged, except the first tape gets written on the square to the right of the tape head with the value of the `j`th symbol of the input. This model is used when considering sub-linear time complexities. Show that a usual Turing Machine can simulate a random access memory Turing Machine and give a time bound that upper bounds the simulation overhead.
5. Consider the language consisting of encodings of Turing Machines that accept only one binary string. Show this language is uncomputable.

Point Breakdown